package com.ztom.top100;

/**
 * 打家劫舍
 * <p>
 * https://leetcode-cn.com/problems/house-robber/
 *
 * @author ZhangTao
 */
public class Code58Rob {

    public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        return process(nums, nums.length - 1);
    }

    /**
     * 以 i 位置结尾, 最大值
     *
     * @param nums
     * @param i
     * @return
     */
    private int process(int[] nums, int i) {
        if (i == 0) {
            // 以 0 位置结尾, 只有一间房
            return nums[0];
        }
        if (i == 1) {
            // 以 1 位置结尾, 只有两间房
            return Math.max(nums[0], nums[1]);
        }
        // 偷了前一间房
        int p1 = process(nums, i - 1);
        // 没偷前一间房
        int p2 = nums[i] + process(nums, i - 2);
        return Math.max(p1, p2);
    }

    public int rob1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        ;
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[nums.length - 1];
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int prepre = nums[0];
        int pre = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int tmp = pre;
            pre = Math.max(pre, nums[i] + prepre);
            prepre = tmp;
        }

        return pre;
    }
}
